Teilgraph

Der Begriff Teilgraph beschreibt in der Graphentheorie eine Beziehung zwischen zwei Graphen. Ein anderes Wort für Teilgraph ist Untergraph. Ein Graph ${\displaystyle H}$ ist Teilgraph des Graphen ${\displaystyle G}$, wenn alle Knoten und Kanten von ${\displaystyle H}$ auch in ${\displaystyle G}$ enthalten sind. Anders gesagt: Ein Teilgraph ${\displaystyle H}$ entsteht aus einem Graphen ${\displaystyle G}$, indem einige Knoten und Kanten aus ${\displaystyle G}$ entfernt werden. Dabei müssen beim Entfernen eines Knotens auch alle inzidenten Kanten mit entfernt werden.